/**
 * https://leetcode.cn/submissions/detail/565040136/
 * 1552. 两球之间的磁力
 * Medium, 黄伟杰 2024.9.16
 * 二分查找
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool check(int n, vector<int> &position, int m) // n是距离，m是个数
    {
        int flag = position[0], cnt = 1; // cnt是在数组里可以塞下多少球
        for (int i = 1; i < position.size(); i++)
        {
            if (position[i] - flag >= n)
            {
                flag = position[i];
                cnt++;
            }
        }
        return cnt >= m; // 球数量够就为turn
    }

public:
    int maxDistance(vector<int> &position, int m)
    {
        sort(position.begin(), position.end());
        int l = 1, r = position.back(), ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (check(mid, position, m))
            {
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        return ans;
    }
};